# -*- coding: utf-8 -*-

import time
import sys
import math
from random import uniform
from time import clock

'''

 autor: António Delgado
 Data: 11-03-2013


'''
class heapsort:
        def __init__(self, A):
                self.A = A
                
        def max_heapify(self, A, i):

                global heapsize
                left = 2 * i
                right = 2 * i + 1


                if left <= heapsize and self.A[left] > self.A[i]:
                        largest = left

                else:
                        largest = i

                if right <= heapsize and self.A[right] > self.A[largest]:
                        largest = right

                if largest != i:
                        self.A[i], self.A[largest] = self.A[largest], self.A[i]
                        self.max_heapify(A, largest)

        def build_max_heap(self, A):
                for i in range(int(math.floor(len(self.A)/2)), 0, -1):
                        self.max_heapify(A, i)

        def heapsort(self, A):
                global heapsize
                heapsize = len(self.A)-1
                self.build_max_heap(A)
                for i in range (len(self.A)-1, 1, -1):
                        self.A[1], self.A[i] = self.A[i], self.A[1]
                        heapsize = heapsize - 1
                        self.max_heapify(A, 1)
                return self.A



A = [sys.maxint, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
i = 1
execucaoOne= time.clock()
print 'Desordenado:', A
H = heapsort(A)
execucaoTwo= time.clock()
print 'Ordenado:', H.heapsort(A)
print 'Time Inicial:', execucaoOne
print 'Time final:', execucaoTwo
print 'Time Final-Inicial:', execucaoTwo-execucaoOne

Z = [1] + range(50, 1050, 50)
T = []
M = 25
for n in Z:
    A = [ uniform(0.0,1.0) for k in xrange(n)]
    tempos = []
    for k in range(M):
        t1 = clock()
        heapsort(A)
        t2 = clock()
        tempos.append(t2-t1)
    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
    
    T.append((n,media, var))

X = [n for n, media, var in T]
Y = [media for n, media, var in T]
ct=15e6
Z = [n * math.log(n)/ct for n, media, var in T]

import matplotlib.pyplot as plt
plt.grid(True)
plt.ylabel(u'T(n) - tempo de execução médio em segundos')
plt.xlabel(u'n - número de elementos')
plt.plot(X,Y,'rs', label="resultado experimental")
plt.plot(X, Z, 'b^', label=u"previsão teórica")
plt.legend()
plt.show()
